α-Conotoxins are disulfide-rich peptide neurotoxins that selectively inhibit neuronal nicotinic acetylcholine receptors (nAChRs). The α3β4 nAChR subtype has been identified as a novel target for managing nicotine addiction. Using a mixture-based positional-scanning synthetic combinatorial library (PS-SCL) with the α4/4-conotoxin BuIA framework, we discovered a highly potent and selective α3β4 nAChR antagonist. The initial PS-SCL consisted of a total of 113 379 904 sequences that were screened for α3β4 nAChR inhibition, which facilitated the design and synthesis of a second generation library of 64 individual α-conotoxin derivatives. Eleven analogues were identified as α3β4 nAChR antagonists, with TP-2212-59 exhibiting the most potent antagonistic activity and selectivity over the α3β2 and α4β2 nAChR subtypes. Final electrophysiological characterization demonstrated that TP-2212-59 inhibited acetylcholine evoked currents in α3β4 nAChRs heterogeneously expressed in Xenopus laevis oocytes with a calculated IC50 of 2.3 nM and exhibited more than 1000-fold selectivity over the α3β2 and α7 nAChR subtypes. As such, TP-2212-59 is among the most potent α3β4 nAChRs antagonists identified to date and further demonstrates the utility of mixture-based combinatorial libraries in the discovery of novel α-conotoxin derivatives with refined pharmacological activity.